Random numbers, which are referred to as the result of random elements, are required for many applications. So-called random number generators are used to generate random numbers. Random number generators are methods which supply a sequence of random numbers. A crucial criterion of random numbers is whether the result of the generation may be regarded as being independent of earlier results.
Random numbers are required for cryptographic methods, for example. These random numbers are used to generate keys for the encryption methods. Such keys are subject to high requirements in terms of the randomness properties. Pseudo random number generators (PRNG), for example, represented by a linear feedback shift register (LFRS), are therefore not suitable for this purpose. Only a true random number generator (TRNG) meets the requirements at hand. This generator uses natural noise processes to obtain an unpredictable result. Noise generators which use the thermal noise of resistors or semiconductors or the shot noise at potential barriers, such as at p-n junctions, are common. Another option is the use of radioactive decay of isotopes.
While “traditional” methods use analog elements, such as resistors, as noise sources, digital elements, such as inverters, have been used frequently in the more recent past. These have the advantage of lower complexity in the circuitry layout since these are available as standard elements. In addition, such circuits may also be used in freely programmable circuits, such as FPGAs.
For example, the use of ring oscillators which represent an electronic oscillator circuit is known. In these, an odd number of inverters is interconnected to form a ring, whereby an oscillation having a natural frequency is created. The natural frequency depends on the number of inverters in the ring, the properties of the inverters, the conditions of the interconnection, namely the line capacitances, the operating voltage and the temperature. Due to the noise of the inverters, a random phase displacement occurs as compared to the ideal oscillator frequency, which is used as a random process for the TRNG. It must be noted that ring oscillators oscillate independently and do not require any external components, such as capacitors or coils.
One problem with the use of randomness arises in that the ring oscillator must be sampled, preferably in the vicinity of an anticipated ideal edge to obtain a random sampled value. The publication by Bock, H., Bucci, M., Luzzi, R.: An Offset-compensated Oscillator-based Random Bit Source for Security Applications, CHES 2005, shows an option of how sampling is always carried out in the vicinity of an oscillator edge by the controlled shifting of the sampling point in time.
A method for generating random numbers with the aid of a ring oscillator is known from the publication European Patent No. 1 686 458, in which a first and a second signal are provided, the sampling of the first signal being triggered by the second signal. In the described method, a ring oscillator is sampled multiple times, always using only non-inverting delays, namely an even number of inverters as delay elements. Starting from a starting point, the oscillator ring is always sampled after an even number of inverters simultaneously or with mutual delay. In this way, the shift of the sampling point in time may be dispensed with; instead, the multiple sampling signals are evaluated.
The publication “Design of Testable Random Bit Generators” by Bucci, M. and Luzzi, R. (CHES 2005) introduces a method with which an influence on the random source may be detected. Attacks may thus be prevented. However, it does not allow a direct distinction between random values and deterministic values.
Another option is provided by the use of multiple ring oscillators. This is demonstrated in the publication Sunar, B. et al: Aproveable Secure True Random Number Generator with Built In Tolerance Attacks, IEEE Trans. on Computers, January 2007, for example. Here, sample values of multiple ring oscillators are concatenated to each other and evaluated.
The problem here is that correlations between the ring oscillators may occur, for example due to outside influences, so that the results obtained do not have a desired degree of entropy.